
import java.util.*;


class Main {
    public static void main(String args[]) {
        int[][] arr = {{2, 3}, {4, 5}, {1, 3}, {7, 8}};
        int[][] merge = merge(arr);
        for (int[] a : merge) {
            System.out.printf("%s\t", Arrays.toString(a));
        }

    }

    public static int[][] merge(int[][] intervals) {
        List<int[]> list = new ArrayList<>();

        //数组第一个元素进行排序，便于后面操作
        Arrays.sort(intervals, (a1, a2) -> {
            return a1[0] - a2[0];
        });
//        初始指针
        int left = 0;
        int right = 0;

        while (right < intervals.length) {
//            定义每层循环的左右边界
            int leftBound = intervals[left][0];
            int rightBound = intervals[right][1];
//如果考虑相邻合并{2,3},{4,5}==>{12,5}
// 需加上||rightBound+1==intervals[right][0]
            while (right < intervals.length &&
                    (intervals[right][0] <= rightBound || rightBound + 1 == intervals[right][0])) {
                rightBound = Math.max(intervals[right][1], rightBound);
                right++;
            }
            list.add(new int[]{leftBound, rightBound});
//            将left移动到right,开启下一轮循环
            left = right;
        }
//        将list转换为int[][]
        int[][] res = new int[list.size()][2];
        for (int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }
}

